package com.squirrel.michale.search4;


/**
 * @author guanhao 观浩
 * @version 1.0.0.0
 * @createTime 2023/1/18 12:15 PM
 * @company Michale Squirrel
 * @link
 * @description
 */

/**
 * 剑指 Offer 53 - II. 0～n-1中缺失的数字
 * 简单
 * 333
 * 相关企业
 * 一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0～n-1之内。在范围0～n-1内的n个数字中有且只有一个数字不在该数组中，请找出这个数字。
 *
 *
 *
 * 示例 1:
 *
 * 输入: [0,1,3]
 * 输出: 2
 * 示例 2:
 *
 * 输入: [0,1,2,3,4,5,6,7,9]
 * 输出: 8
 *
 *
 * 限制：
 *
 * 1 <= 数组长度 <= 10000
 */
public class Offer0053 {

    public int missingNumber(int[] nums) {


        int left = 0;
        int right = nums.length;

        int target = 0;
        while (left <= right) {
            target = left + ((right - left) >> 1);

            if (target == nums.length) {
                return nums.length;
            } else if (target < nums[target]){
                right = target -1;
            }else {
                return target;
            }
        }
        return target;

    }


    public int missingNumber2(int[] nums) {
        // 对于有序数组, 大小为i的数应当处于下标为i的位置上, 如果不在, 说明在该数字之前发生了错位
        int left = 0, right = nums.length - 1;
        while (left < right) {
            int mid = left + ((right - left) >> 1);
            if (nums[mid] != mid) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        // 如果从0 ~ n - 1都不缺值, 则缺少的是n
        return left == nums.length - 1 && nums[left] == left ? left + 1 : left;
    }

    public static void main(String[] args) {
        int[] nums = new int[]{0, 1, 2, 3, 4, 5, 6, 7, 9};

        Offer0053 offer0053 = new Offer0053();
//        System.out.println(offer0053.missingNumber(nums));

        int[] nums2 = new int[]{0};

//        System.out.println(offer0053.missingNumber2(nums2));


        int[] nums3 = new int[]{0, 1, 2, 3, 4, 5, 6, 7, 8};

//        System.out.println(offer0053.missingNumber2(nums3));


        int[] nums4 = new int[]{0, 2, 3, 4, 5, 6, 7, 8,9,10};

        System.out.println(offer0053.missingNumber2(nums4));
    }

}
